Методы фильтрации обучающей выборки
Knn Метод ближайших соседей не требует обучения, Сложность предсказания O(KD) . При большом количестве объектов возникает проблема, связанная с большим объемом вычислений для нахождения ближайшего соседа для распознаваемого объекта. Для борьбы с этой проблемой могут применяться методы фильтрации обучающей выборки или же структуризация пространства. Методы фильтрации Удаление выбросов. Рассмотрим отступы M(x_i, c_j) = g_{c_j}(x_i) - \underset{c \in \mathbf{C} \backslash \{c_j\}}{\max}g_{c}(x_i) и удалим все объекты, которые являются выбросами, т.е. {x_i: M(x_i, c_j) < \delta, \delta < 0} . \textbf{C} — множество всех классов. Алгоритм STOLP по версии Воронцова Эталоны * Эталоны — это такое подмножество выборки X^l , что все объекты X^l (или их большая часть) классифицируются правильно при использовании в качестве обучающей выборки множества эталонов. * Эталонами i -го класса при классификации методом ближайшего соседа может служить такое подмножество объектов этого класса, что расстояние от любого принадлежащего ему объекта из выборки X^l до ближайшего «своего» эталона меньше, чем до ближайшего «чужого» эталона. Простой перебор для отбора эталонов не эффективен, так как число способов выбора по t эталонов для каждого класса (число классов k ) составляет \prod_{j=1}^k C_{m_j}^t . Алгоритм STOLP позволяет сократить этот перебор Величина риска Величина риска ( W ) — величина, характеризующая степень риска для объекта быть классифицированным не в тот класс, которому он принадлежит. * При использовании метода ближайшего соседа можно считать W(x_i)=\rho_{in}(x_i)/\rho_{out}(x_i) , где \rho_{in} — расстояние от объекта x_i до ближайшего к нему объекта (или эталона) из «своего» класса, \rho_{out} — до ближайшего объекта (или эталона) «чужого» класса. * При использовании любого метрического метода можно положить W(x_i)=-M(x_i, \Omega) , где M(x_i, \Omega)=\Gamma_{y_i}-\max_{y \in \mathbb{Y} \setminus y_i} \Gamma_y (x_i) — отступ на объекте x_i при обучающей выборке \Omega , где \Omega — множество эталонов. Кроме того, в зависимости от используемого метода классификации можно подобрать и другие оценки величины риска. Главное, чтобы они принимали большие значения на объектах-выбросах, меньшие — на объектах, находящихся на границе класса, и еще меньшие — на объектах, находящихся в глубине своего класса. Алгоритм STOLP Вход * Выборка X^l * Допустимая доля ошибок l_0 * Порог отсечения выбросов \delta * Алгоритм классификации * Формула для вычисления величины риска W Описание алгоритма * Отбросить выбросы (объекты X^l с W > \delta ) * Сформировать начальное приближение \Omega — из объектов выборки X^l выбрать по одному объекту каждого класса, обладающему среди объектов данного класса максимальной величиной риска либо минимальной величиной риска * Наращивание множества эталонов (пока доля числа объектов выборки X^l , распознаваемых неправильно, не станет меньше l_0 ): ** Классифицировать объекты X^l , используя в качестве обучающей выборки \Omega ** Пересчитать величины риска для всех объектов X^l \setminus \Omega с учетом изменения обучающей выборки ** Среди объектов каждого класса, распознанных неправильно, выбрать объекты с максимальной величиной риска и добавить их к \Omega Результат Множество эталонов \Omega \in X^l для каждого класса представляет собой некоторый набор объектов, находящихся на границе класса, и, если в качестве начального приближения выбирались объекты с минимальной величиной риска, один объект, находящийся в центре класса. Алгоритм удаления неинформативных объектов по версии Китова Идея: удалить неинформативные объекты, которые не дают информации о классе, которому они принадлежат. * for each class c = 1, 2, \ldots C #add the most ** x© = \mathrm{arg}\max_{x_i: c_i = c}(M(x_i,c_i)) # representative example * Initialize etalons: \Omega = \{ x©, c =1, 2, \ldots C \} * repeat while accuracy significantly increases ** x_i = \mathrm{arg}\max_{x_i \in TS \backslash \Omega}(M(x,\Omega)) # add object ** \Omega = \Omega \cup \{x_i\} #''with smallest margin'' * return \Omega Краткое содержание: сначала добавляем объекты по одному на класс с наибольшим отступом. А потом, пока увеличивается точность, добавляем с наименьшим отступом. Ссылки Китовослайды Алгоритм STOLP